import java.util.*;
/**
 * DP42 【模板】完全背包
 * https://www.nowcoder.com/practice/237ae40ea1e84d8980c1d5666d1c53bc?tpId=230&tqId=2032575&ru=/exam/oj&qru=/ta/dynamic-
 * programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196
 */
public class Exerciser5 {
    static int N = 1010;

    /**
     * 滚动数组进行优化
     * @param args
     */
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int V = in.nextInt();
        int[] v = new int[N];
        int[] w = new int[N];

        for(int i = 1;i <= n;i++) {
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        int[] dp = new int[V + 1];
        // 第一问
        // 初始化，新增的第一行的所有列为0，第一列的所有行是不需要进行初始化的，因为已经进行特判了
        for(int i = 1;i <= n;i++) {
            for(int j = v[i];j <= V;j++) {
                // 从上到下，从左到右
                dp[j] = Math.max(dp[j],dp[j - v[i]] + w[i]);
            }
        }
        System.out.println(dp[V]);

        // 第二问
        // dp在上一问中用过了，这里需要清空
        Arrays.fill(dp,0);
        // 设置：dp[i][j] = -1 说明在前i个数中选取的值的体积和是等于不了j的，说明没有，就判为-1
        // 初始化，新增的第一行的j从1~V的区间的值均为-1,第一列的所有行是不需要进行初始化的，因为已经进行特判了
        for(int j = 1;j <= V;j++) {
            dp[j] = -1;
        }
        for(int i = 1;i <= n;i++) {
            for(int j = v[i];j <= V;j++) {
                if(dp[j - v[i]] != -1) {
                    dp[j] = Math.max(dp[j],dp[j - v[i]] + w[i]);
                }
            }
        }
        System.out.println(dp[V] == -1 ? 0 : dp[V]);
    }

    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int V = in.nextInt();
        int[] v = new int[N];
        int[] w = new int[N];

        for(int i = 1;i <= n;i++) {
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        // 第一问：
        // dp[i][j]: 从前i个数挑选，总体积不超过j，最大的价值
        // 第二问：
        // dp[i][j]: 从前i个数挑选，总体积正好等于j，最大的价值
        int[][] dp = new int[n + 1][V + 1];
        // 第一问
        // 初始化，新增的第一行的所有列为0，第一列的所有行是不需要进行初始化的，因为已经进行特判了
        for(int i = 1;i <= n;i++) {
            for(int j = 0;j <= V;j++) {
                // 从上到下，从左到右
                dp[i][j] = dp[i -1][j];
                if(j >= v[i]) {
                    dp[i][j] = Math.max(dp[i][j],dp[i][j - v[i]] + w[i]);
                }
            }
        }
        System.out.println(dp[n][V]);

        // 第二问
        // dp在上一问中用过了，这里需要清空
        for(int i = 0;i <= n;i++) {
            Arrays.fill(dp[i],0);
        }
        // 设置：dp[i][j] = -1 说明在前i个数中选取的值的体积和是等于不了j的，说明没有，就判为-1
        // 初始化，新增的第一行的j从1~V的区间的值均为-1,第一列的所有行是不需要进行初始化的，因为已经进行特判了
        for(int j = 1;j <= V;j++) {
            dp[0][j] = -1;
        }
        for(int i = 1;i <= n;i++) {
            for(int j = 0;j <= V;j++) {
                dp[i][j] = dp[i - 1][j];
                if(j >= v[i] && dp[i][j - v[i]] != -1) {
                    dp[i][j] = Math.max(dp[i][j],dp[i][j - v[i]] + w[i]);
                }
            }
        }
        System.out.println(dp[n][V] == -1 ? 0 : dp[n][V]);
    }
}
